package sort;
/**
 * <b>冒泡排序</b>
 * @author 威 
 * <br>2018
 */
public class Sort{
	/**
	 * 基本冒泡排序 升序
	 * <p>	 
	 * 是稳定的 时间复杂度为O(2n)
	 * @param a
	 * @param len
	 * @return
	 * int[]
	 */
	public int[] sort(int[] a, int len){
		for(int i = 0; i < len; i++){
			for(int j = 0; j < len - i - 1; j++){
				if(a[j] > a[j+1]){
					int temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}
		return a;
	}
	/**
	 * 基本冒泡排序加强
	 * <p>
	 * 当数组排序步骤没结束，但是已经是有序的了，那么直接退出整个排序	 
	 * @param a
	 * @param len
	 * @return
	 * int[]
	 */
	public int[] sort2(int[] a, int len){
		for(int i = 0; i < len; i++){
			boolean isFlag = true;
			for(int j = 0; j < len - i - 1; j++){
				if(a[j] > a[j+1]){
					isFlag = false;
					int temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
			if(isFlag)
				break;
		}
		return a;
	}
	public static void main(String[] args){
		long[] avgs = new long[10]; 
		for(int i = 0; i < 1; i++){
			int[] a = com.chen.test.Data.getData();
			long temp;
			long start = System.currentTimeMillis();
			
	//		平均33毫秒
//			new Sort().sort(a, a.length);
			
//			平均34毫秒
//			new Sort().sort2(a, a.length);
			
//			平均2毫秒
//			new QuickSort().quickSort(a, 0, a.length-1);
			
//			平均16毫秒
//			new InsertSort().insertSort(a, a.length);
			
//			平均3毫秒
//			new ShellSort().shellSort(a, a.length);
		
//			平均29毫秒
//			new SelectionSort().selectSort(a, a.length);
			
//			平均2/3毫秒
//			new MergeSort().mergeSort(a, a.length);
			
//			平均3毫秒
//			new RadixSort().redixSort(a, 2);
			
//			平均2/3毫秒
//			new HeapSort().headSort(a, a.length);
			
			temp = (System.currentTimeMillis() - start);
			System.out.println(temp);
			/*avgs[i] = temp;
			try {
				Thread.sleep(500);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}*/
			a = null;
		}
		/*long sum = 0;
		for(long item : avgs){
			sum+=item;
		}
		double d = sum/10;
		System.out.println(d);*/
	}
}